package com.cowin.inf.model.linkedlist;

import com.cowin.inf.model.vo.VehicleRouteVo;
import io.swagger.models.auth.In;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (C), 1998-2019, 奇瑞信息
 *
 * @author : 于超
 * @Date: 2019/11/26 13:00
 * @Description:
 */
public class SingleLinkedList {

    //先初始化一个头节点 头结点不要动
    private VehicleNode head = new VehicleNode("0", 0, null);

    public VehicleNode getHead() {
        return head;
    }

    public void addByOrder(VehicleRouteVo vehicleRouteVo, Integer type) {
        //因为head节点 不能动 因此需要一个辅助变量(指针) temp 找到添加的位置
        //因为 是 单链表 因此 找的temp 是 添加位置的前一个节点 否则 插入不了
        String no = "";
        if (0 == type) {
            no = vehicleRouteVo.getLotId();
        } else if (1 == type) {
            no = vehicleRouteVo.getCarColor();
        } else if (2 == type) {
            no = vehicleRouteVo.getCarType();
        } else if (3 == type) {
            if (vehicleRouteVo.getCreateTime() != null) {
                no =vehicleRouteVo.getCreateTime().toString();
            }


        }
        VehicleNode temp = head;
        boolean flag = false; //表示 添加的编号 是否存在 默认false
        while (true) {
            if (temp.next == null) {
                //说明temp已经在链表的最后
                break;
            }
            if (temp.next.no.equals(no)) {
                //位置 找到 在temp之后
                flag = true;
                break;
            }
            temp = temp.next; //后移 继续遍历
        }
        if (flag) {
            temp.next.setSize(temp.next.getSize() + 1);
            temp.next.getVehicleRouteVo().add(vehicleRouteVo);
        } else {
            //插入链表 temp后面
            List<VehicleRouteVo> list = new ArrayList<>();
            list.add(vehicleRouteVo);
            VehicleNode vehicleNode = new VehicleNode(no, 1, list);
            temp.next = vehicleNode;
        }


    }
    public void add(VehicleNode heroNode) {

        //因为head节点不能动，因此我们需要一个辅助遍历 temp
        VehicleNode temp = head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if(temp.next == null) {//
                break;
            }
            //如果没有找到最后, 将将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }

    public VehicleNode getSingleLinkedNodeList(List<VehicleRouteVo> list, Integer type) {
        list.forEach(e -> {
            addByOrder(e, type);
        });
        //颜色 反转最多的列表
        if (1 == type) {
            sortList(head);
            reversetList(head);
        }
        return head;
    }

    public VehicleNode sortList(VehicleNode head) {
        //采用归并排序
        if (head == null || head.next == null) {
            return head;
        }
        //获取中间结点
        VehicleNode mid = getMid(head);
        VehicleNode right = mid.next;
        mid.next = null;
        //合并
        return mergeSort(sortList(head), sortList(right));
    }

    private VehicleNode getMid(VehicleNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //快慢指针
        VehicleNode slow = head, quick = head;
        //快2步，慢一步
        while (quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        return slow;
    }

    /**
     * 归并两个有序的链表
     *
     * @param head1
     * @param head2
     * @return
     */
    private VehicleNode mergeSort(VehicleNode head1, VehicleNode head2) {
        VehicleNode p1 = head1, p2 = head2, head;
        //得到头节点的指向
        if (head1.getSize() < head2.getSize()) {
            head = head1;
            p1 = p1.next;
        } else {
            head = head2;
            p2 = p2.next;
        }

        VehicleNode p = head;
        //比较链表中的值
        while (p1 != null && p2 != null) {
            if (p1.getSize() <= p2.getSize()) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            } else {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        //第二条链表空了
        if (p1 != null) {
            p.next = p1;
        }
        //第一条链表空了
        if (p2 != null) {
            p.next = p2;
        }
        return head;
    }
    public static VehicleNode reversetList(VehicleNode head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return head;
        }

        //定义一个辅助的指针(变量)，帮助遍历原来的链表
        VehicleNode cur = head.next;
        VehicleNode next = null;// 指向当前节点[cur]的下一个节点
        VehicleNode reverseHead = new VehicleNode("0", 0, null);
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        //动脑筋
        while(cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; //将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
        return head;
    }
}
